/*
 * Introduction to algorithms
 * Second Edition
 * P143
 * Young tableaus
 */
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>

#define X 14
#define Y 25

int a[X][Y];
/*
 * Insert a number to tableaus
 */
void insert(int a[][Y], int x, int y, int num)
{
	a[x - 1][y - 1] = num;
	int m = x - 1;
	int	n = y - 1;
	int maxi;
	int maxj;
	
	while(m > 0 || n > 0)
	{
		if(m > 0 && n > 0)
		{
			if(a[m - 1][n] >= a[m][n - 1])
			{
				maxi = m -1;
				maxj = n;
			}//end if(a[m - 1][n] >= a[m][n - 1])
			else 
			{
				maxi = m;
				maxj = n -1;
			}//end else
		}//end if(m > 0 && n > 0)
		else if(m == 0)
		{
			maxi = 0;
			maxj = n -1;
		}//end else if(m == 0)
		else 
		{
			maxi = m -1;
			maxj = 0;
		}//end else

		if(a[m][n] >= a[maxi][maxj])
		{
			break;
		}//end if(a[m][n] >= a[maxi][maxj])
		else
		{
			int temp = a[m][n];
			a[m][n] = a[maxi][maxj];
			a[maxi][maxj] = temp;

			m = maxi;
			n = maxj;
		}//end else
	}//end while
}

int find_x(int a[][Y], int sx, int sy, int ex, int ey, int num)
{
	if(a[sx][sy] > num)
	{
		return -1;
	}//end if
	int i = sx, j = sy;
	while(i <= ex && j <= ey)
	{
		if(a[i][j] < num)
		{
			i++;
			j++;
		}//end if(a[i][j] < num)
		else if(a[i][j] == num)
		{
			return 1;
		}//end else if(a[i][j] == num)
		else 
		{
			break;
		}//end else
	}//end while
	if(i > ex && j <= ey)
		return find_x(a, sx, j, ex, ey, num);
	else if(j > ey && i <= ex)
		return find_x(a, i, sy, ex, ey, num);
	else if(i > ex && j > ey)
		return -1;
	else 
	{
		if(find_x(a, sx, j, ex, ey, num) + find_x(a, i, sy, ex, ey, num) > -2)
			return 1;
		else return -1;
	}//end else
}
/*
 * find number in matrix
 * the left top point of matrix is (sx, sy)
 * the right bottom point of matrix is (ex, ey)
 */
int find(int a[][Y], int sx, int sy, int ex, int ey, int num)
{
	//sleep(1);
	//printf("*%d,%d,%d,%d\n", sx, sy, ex, ey);
	int i = sx, j = sy;
	//printf("**%d,%d,%d,%d\n", sx, sy, ex, ey);
	if(sx == ex)
	{
		//printf("sx == ex\n");
		int k;
		for(k = sy; k <= ey; k++)
		{
			//printf("k:%d\n", k);
			if(a[sx][k] == num)
			{
				return 1;
			}//end if(a[sx][k] == num)
		}//end for
		return -1;
	}//end if(sx == ex)
	if(sy == ey)
	{
		//printf("sy == ey\n");
		int k;
		for(k = sx; k <= ex; k++)
		{
			//printf("k:%d\n", k);
			if(a[k][ey] == num)
			{
				return 1;
			}//end if(a[k][ey] == num)
		}//end for
		//printf("end for\n");
		return -1;
	}//end if(sy == ey)
	if(a[sx][sy] > num)
	{
		int k;
		for(k = sx + 1; k <= ex; k++)
			if(a[k][sy] == num)
				return 1;
		for(k = sy + 1; k<= ey; k++)
			if(a[sx][k] == num)
				return 1;
		return find_x(a, sx + 1, sy + 1, ex, ey, num);
	}//end if(a[sx][sy] > num)
	while(i <= ex && j <= ey)
	{
		if(a[i][j] < num)
		{
			i++;
			j++;
		}//end if(a[i][j] < num)
		else if(a[i][j] == num)
		{
			return 1;
		}//end else if(a[i][j] == num)
		else
		{
			break;
		}//end else
	}//end while(i <= ex && j <= ey)
	if(i == ex && j == ey && num > a[i][j])
	{
		return -1;
	}//end if(i == ex && j == ey && num > a[i][j])
	if(i > ex)
		return find_x(a, sx, j, ex, ey, num);
	else if(j > ey)
		return find_x(a, i, sy, ex, ey ,num);
	else
	{
		int left = find_x(a, i, sy, ex, j, num);
		if(left == 1)
			return left;
		int right = find_x(a, sx, j, ex, ey, num);
		if(left == -1 && right == -1)
			return -1;
		else return 1;
	}//end else
}
/*
 * print tableaus
 */
void print(int a[][Y], int x, int y)
{
	printf("\n*****start*****\n");
	
	int i,j;
	for(i = 0; i < x; i++)
	{
		for(j = 0; j < y; j++)
		{
			if(a[i][j] < INT_MAX)
			{
				printf("%-5d", a[i][j]);
			}//end if(a[i][j] < INT_MAX) 
			else 
			{
				printf("     ");
			}//end else
		}//end for
		printf("\n");
	}
	printf("\n******end******\n");
}

void initial(int a[][Y], int x, int y)
{
	int i, j;
	for(i = 0; i < x; i++)
	{
		for(j = 0; j < y; j++)
		{
			a[i][j] = INT_MAX;
		}//end for

	}//end for
}

int seq_search(int *a, int n, int num)
{
	int i;
	for(i = 0; i < n; i++)
	{
		if(a[i] == num)
			return 1;
	}//end for
	return -1;
}

int test()
{
	initial(a, X, Y);
	srand(time(0));

	int data[X * Y - 5];

	int i;
	int findn;
	for(i = 0; i < X * Y - 5; i++)
	{
		int r = rand() % 100;
		if(i == X * Y / 2)
		{
			findn = r;
		}//end if(i == X * Y / 2)
		insert(a, X, Y, r);
		data[i] = r;
	}//end for

	//print(a, X, Y);
	//printf("find:%d\n", findn);
	/*
	if(seq_search(data, sizeof(data), findn) == find_x(a, 0, 0, X - 1, Y - 1, findn))
	{
		printf("OK!\n");
	}
	else 
		printf("NO!\n");
	*/
	//printf("%d, %d", seq_search(data, X * Y - 5, findn + 1), find_x(a, 0, 0, X - 1, Y - 1, findn + 1));
	if(seq_search(data, X * Y - 5, findn + 1) != find(a, 0, 0, X - 1, Y - 1, findn + 1))
	{
		printf("NO!\n");
	}//end if(seq_search(data, X * Y - 5, findn + 1) != find(a, 0, 0, X - 1, Y - 1, findn + 1))
}

int main()
{
	while(1)
	{
		test();
		//sleep(1);
	}//end while(1)
}
